void QuickSortCircle(int* arr, int L, int R) //非递归的快排
{
	ST stack;
	StackInit(&stack);
	StackPush(&stack, L);
	StackPush(&stack, R);

	while (!StackEmpty(&stack))
	{
		int right = StackTop(&stack);
		StackPop(&stack);
		int left = StackTop(&stack);
		StackPop(&stack);

		int mid = Partion1(arr, left, right);
		if (mid+1< R)
		{
			StackPush(&stack, mid + 1);
			StackPush(&stack, right);
		}
		if (left < mid -1)
		{
			StackPush(&stack, left);
			StackPush(&stack, mid-1);
		}
	}
	StackDestory(&stack);
}
void _QuickSort(int* arr, int L, int R) //前后指针法
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int first = arr[L];
	while (left < right)
	{
		while (left < right && arr[right] >= first)
		{
			right--;
		}
		while (left < right && arr[left] <= first)
		{
			left++;
		}
		swap(&arr[left], &arr[right]);
	}
	swap(&arr[left], &arr[L]);
	_QuickSort(arr, L, right - 1);
	_QuickSort(arr, right+1, R);
}
void QuickSort(int* arr, int L, int R) //挖坑法
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int first = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= first)
		{
			right--;
		}

		if (left < right)
		{
			arr[left] = arr[right];
		}

		while (left < right && arr[left] <= first)
		{
			left++;
		}

		if (left < right)
		{
			arr[right] = arr[left];
		}

		if (left == right)
		{
			arr[left] = first;
		}
	}
	QuickSort(arr, L, left - 1);
	QuickSort(arr, left + 1, R);
}
void hoareQuickSort(int* arr, int L, int R) //hoare法
{
	if (L >= R)
	{
		return;
	}
	if ((R - L+1) < 15) //小区间优化
	{
		InsertSort(arr + L, R+1);
	}
	int mid = Getmid(arr, L, R); //三数取中
	swap(arr[L], arr[mid]);
	int left = L;
	int right = R;
	int key = arr[L];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		if (left < right)
		{
			swap(arr[left], arr[right]);
		}
	}
	swap(&arr[left], &arr[L]);
	hoareQuickSort(arr, L, left - 1);
	hoareQuickSort(arr, left + 1, R);
}
int Getmid(int* arr, int L, int R)
{
	int mid = L + (R - L) / 2;
	if (arr[L] > arr[mid])
	{
		if (arr[mid] > arr[R])
		{
			return mid;
		}
		else if (arr[L] > arr[R])
		{
			return R;
		}
		else
		{
			return L;
		}
	}
	else //arr[L] < arr[mid]
	{
		if (arr[L] > arr[R])
		{
			return L;
		}
		else if (arr[mid] > arr[R])
		{
			return R;
		}
		else
		{
			return mid;
		}
	}
}
void ThreeQuickSort(int* arr, int L, int R) //三路划分法
{
	if (L >= R)
	{
		return;
	}
	if ((R - L + 1) < 15)
	{
		InsertSort(arr+L, (R - L + 1));
	}
	else
	{
		int mid = Getmid(arr, L, R);
		swap(arr[mid], arr[L]);
		int left = L;
		int cur = L + 1;
		int first = arr[L];
		int right = R;
		while (cur <= right)
		{
			if (arr[cur] < first)
			{
				swap(arr[cur], arr[left]);
				cur++;
				left++;
			}
			else if (arr[cur] > first)
			{
				swap(arr[cur], arr[right]);
				right--;
			}
			else //arr[cur] == first
			{
				cur++;
			}
		}
		//[L,left-1][left,right][right+1,R]
		ThreeQuickSort(arr, L, left -1);
		ThreeQuickSort(arr, right + 1, R);
	}
}